package Leetcode2.链表;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Algo739 {

    //[]
    public static void main(String[] args) {
        int[] param = {1,2,1};
        int[] nums = nextGreaterElements(param);

        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }

    public static int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack<Integer> s = new Stack<>();

        for (int i = temperatures.length - 1; i >= 0; i--) {
            while (!s.isEmpty() && temperatures[i] >= temperatures[s.peek()]) {
                s.pop();
            }
            result[i] = s.isEmpty()? 0: s.peek() - i;
            s.add(i);
        }
        return result;
    }

    //0 1 2 3 4 5

    //[1,2,1]   [2,-1,2]
    public static int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];
        Stack<Integer> s = new Stack<>();

        for (int i = nums.length * 2-1; i >= 0; i--) {
            int j = i%nums.length;
            while (!s.isEmpty() && nums[j]>=s.peek()) {
                s.pop();
            }
            result[j] = s.isEmpty()? -1:s.peek();
            s.add(nums[j]);
        }
        return result;
    }
}
